package com.arron.algorithm.leetcodetop100;



import org.omg.CORBA.NO_IMPLEMENT;

import java.util.HashMap;
import java.util.Map;


/**
 * Leetcode 146. LRU 缓存
 */
public class LRUCache {

    class Node{
        public int val;
        public int key;
        public Node pre;
        public Node next;

        public Node(int k,int v){
            this.key = k;
            this.val = v;
        }

        public Node(){

        }

    }

    public Node head;
    public Node tail;
    public int cap;
    public int size;
    public Map<Integer,Node> map;



    public LRUCache(int capacity){
        cap = capacity;
        map = new HashMap<>(capacity);
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }


    public void put(int key, int value){
        Node node = map.get(key);

        if (node != null){
            //添加到头节点
            removeNodeToHead(node);
            node.val = value;
        }else {
            node = new Node(key,value);
            size++;
            addtoHead(node);
            if (size>cap){
                //删除队列末尾节点
                Node lastnode = tail.pre;
                deleteNode(lastnode);
                //map中删除该元素
                map.remove(lastnode.key);
                //添加到头节点
                size--;
            }

            map.put(key,node);
        }



    }

    private void addtoHead(Node node) {

        node.pre = head;
        node.next = head.next;

        head.next.pre = node;
        head.next = node;

    }



    public int get(int key){

        Node node = map.get(key);
        if (node == null){
            return -1;
        }
        //将节点移动到队列头部
        removeNodeToHead(node);

        return node.val;
    }

    private void removeNodeToHead(Node node) {

        //删除原来得节点
        deleteNode(node);
        addtoHead(node);

    }

    private void deleteNode(Node node) {
        node.next.pre = node.pre;
        node.pre.next = node.next;
        node.next=null;
        node.pre = null;

    }


    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        //"put","put","get","put","get","put","get","get","get"]
        // [1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
        lruCache.put(2,1);
        lruCache.put(2,2);
        lruCache.get(2);
        lruCache.put(1,1);
//
//        lruCache.put(4,1);
//        lruCache.get(1);
//        lruCache.get(3);
        lruCache.get(2);


    }


}


